An Elementary Proof of the Cayley Formula Using Random Maps

摘要

Cayley's formula states that the number of labelled trees on $n$ vertices is$n^{n-2}$, and many of the current proofs involve complex structures orrigorous computation. We present a bijective proof of the formula by providingan elementary calculation of the probability that a cycle occurs in a randommap from an $n$-element set to an $n+1$-element set.